Computing systems may share information maintained in various repositories, such as file systems, databases and so forth. In some cases, two or more computing systems may each maintain a copy of a repository, which is synchronized between the various computing systems. In other cases, a computing system acting as a client may retrieve subsets of the files, documents or other records stored on a computing device that is acting as a server. In these and other cases, information may be shared between the computing devices to provide an indication of the status of records maintained in the repository or on another computing device. Computing systems may, for example, perform comparisons between the collections of documents, files or other records they each possess, in order to synchronization their respective repositories and for various other reasons.
In some cases, there may be a large number of documents, files or other records maintained in a repository. Representations of the state of the repository, including indications of records that have been modified, may therefore occupy a considerable quantity of memory. In some cases data may change frequently, resulting in considerable network bandwidth consumption as record status indications are sent between various computing systems over a network. Compact representations of record status may be difficult to construct, in part due to the large number of records that may be maintained in a repository.